import random
import numpy as np
def headsift(arr,k,length):
    i=k
    j=2*i+1
    while(j<length):
        if(j+1<length and arr[j]<arr[j+1]):
            j+=1
        if(arr[i]>arr[j]):
            break
        else:
            arr[i],arr[j]=arr[j],arr[i]
            i=j
            j=2*i+1

def heapsort(arr):
    l=len(arr)
    for i in range(l//2-1,-1,-1):
        headsift(arr, i, l)
    for i in range(1,l):
        arr[0],arr[l-i]=arr[l-i],arr[0]
        headsift(arr, 0, l-i)        

def insertion_sort(ls):
    for i in range(0,len(ls)):
        current_index = i
        while ls[current_index - 1] > ls[current_index] and current_index - 1 >= 0:
            ls[current_index] , ls[current_index - 1] = ls[current_index - 1] , ls[current_index]
            current_index -= 1
    return ls
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right): #合并两个列表
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):#左右列表分别进行归并，肯定有一个列表先归并完
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]#归并左子列表剩余元素
    result += right[j:]#归并右子列表剩余元素
    return result

def  maopao_sort(nums):
    for i in range(len(nums),0,-1):
        flag = 0
        for j in range(i-1):
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
                flag = 1
        if not flag:
            break
    return nums

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x > pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x < pivot]
    return quick_sort(left) + middle + quick_sort(right)

